package com.my.algorithmlearning.leetcode;

import org.springframework.util.Assert;

import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @ClassName Medium_139_WordBreak
 * @Description 参考题解：https://leetcode.cn/problems/word-break/solution/dan-ci-chai-fen-ju-jue-zhuang-xcong-jian-dan-de-xi/
 * @Author wanghaiwei
 * @Date 2023/4/26 16:18
 */
public class Medium_139_WordBreak {
    public boolean wordBreak(String s, List<String> wordDict) {
        if (wordDict == null || wordDict.size() == 0) {
            return false;
        }
        if (s == null || s.length() <= 0) {
            return false;
        }
        if (wordDict.contains(s)) {
            return true;
        }
        Map<String, Boolean> wordMap = new HashMap<>();
        int maxWordLength = wordDict.get(0).length();
        int minWordLength = wordDict.get(0).length();
        for (String word : wordDict) {
            wordMap.put(word, true);
            if (word.length() > maxWordLength) {
                maxWordLength = word.length();
            }
            if (word.length() < minWordLength) {
                minWordLength = word.length();
            }
        }
        boolean[] dp = new boolean[s.length() + 1];
        dp[0] = true;
        for (int i = 1; i <= s.length(); i++) {
            for (int j = i - 1; j >= 0; j--) {
                dp[i] = dp[j] && checkSingleWord(s.substring(j, i), maxWordLength, minWordLength, wordMap);
                if (dp[i]) {
                    break;
                }
            }
        }
        return dp[s.length()];
    }

    private boolean checkSingleWord(String word, int maxWordLength, int minWordLength, Map<String, Boolean> wordMap) {
        if (word.length() > maxWordLength) {
            return false;
        }
        if (word.length() < minWordLength) {
            return false;
        }
        return wordMap.getOrDefault(word, false);
    }

    public static void main(String[] args) {
        Medium_139_WordBreak solution = new Medium_139_WordBreak();
        Assert.isTrue(solution.wordBreak("leetcode", Arrays.asList("leet", "code")), "Input: s = \"leetcode\", wordDict = [\"leet\",\"code\"] 计算错误，预期true");
    }
}
